package 剑指offer.demo1;//https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
/**
 * 注：找出长度超过一半的
 * 方法1：哈希表确定数组中每个值对应出现的次数比较其是否大于一半
 * 方法2：某元素出现次数大于一半时，排序区间中间元素必是他，直接取中间验证出现次数
 * 方法3：在确定有元素超一半时，相同加次数不想等减次数，最后的值一定是过一半的值
 */
public class 数组中出现次数超过一半的数字 {
    public static int MoreThanHalfNum_Solution_1(int [] array) {
        Map<Integer , Integer> map = new HashMap();
        //循环遍历数组的每个值把他放到哈希表中
        for (int i = 0; i < array.length; i++) {
            //如果当前元素存在，取出来为当前出现过的次数加1，没出现过默认值给0；
            map.put(array[i] , map.getOrDefault(array[i] , 0) + 1);
            //当元素出现次数大于一半时返回
            if (map.get(array[i]) > array.length >> 1)
                return array[i];
        }
        return 0;
    }
    public int MoreThanHalfNum_Solution_2(int [] array) {
        //临时计数
        int count = 0;
        //对数组进行排序
        Arrays.sort(array);
        //找出中位元素，因为长度超一半排序后中位数必须是他
        int mid = array[array.length >> 1];
        //验证其出现次数是否大于一半
        for (int i = 0; i < array.length; i++) {
            if (array[i] == mid) {
                count++;
            }
        }
        //验证是否出现次数大于一半
        if (count > array.length >>1){
            return mid;
        }
        return 0;
    }
    public int MoreThanHalfNum_Solution_3(int [] array){
        int con = array[0];
        int times = 1;
        //这个
        for (int i = 1; i < array.length; i++) {
            //次数为0时，说明他出现次数已经刚好是数过的一半了
            if (times == 0){
                con = array[i];
                times = 1;
            }
            //次数还有时，此时con值就是出现次数最多的，如果还等于就相加1，否则最大值减1
            if (con == array[i])
                times++;
            else times--;
        }
        return con;
//因为题目已经明确这个值必存在，所以此时的con值必是，否则要下面这些进行确认
//        times = 0;
//        for (int i = 0; i < array.length; i++) {
//            if (array[i] == con){
//                times ++;
//            }
//            if (times > array.length >> 1){
//                return con;
//            }
//        }
//        return 0;
    }
}
